In this example, we are going to learn how to make a recommendation system using collaborative filtering. Collaborative filtering is one of the most common approaches used to recommend products or services to customers and became very popular after the famous Netflix competition. By creating a collaborative filtering algorithm with keras, you will also be exposed to how we can create more customized models with keras’ functional model options.

Learning objectives:

Requirements

library(keras)
library(tidyverse)
library(glue)

Prepare our data

For this module we’ll use MovieLens data, which provides user rating information for movies. There are multiple dataset sizes; however, for efficiency we will use the smaller dataset that contains 100,836 ratings of 9,724 movies rated by 610 users.

data_dir <- here::here("materials", "data", "ml-latest-small")
movies <- read_csv(file.path(data_dir, "movies.csv"))
ratings <- read_csv(file.path(data_dir, "ratings.csv"))

Currently our datasets are separate and movie ID ranges from 1 to 193,609 even though our data only contains 9,724 unique movie IDs. Consequently, the following creates a dense_movie_id so there are no gaps, which makes future mapping of our word vector to embeddings simpler, and also joins our datasets and cleans up our column names.

movie_data <- ratings %>% 
  distinct(movieId) %>%
  rowid_to_column(var = "dense_movie_id") %>%
  inner_join(ratings) %>%
  inner_join(movies) %>%
  select(user_id = userId, movie_id = movieId, dense_movie_id, rating, everything())

movie_data

Let’s extract the number of movies and users. We’ll use these parameters later in our keras model.

n_movies <- n_distinct(movie_data$dense_movie_id)
n_users <- n_distinct(movie_data$user_id)

glue("This dataset includes {nrow(movie_data)} ratings by {n_users} users on {n_movies} unique movies")
This dataset includes 100836 ratings by 610 users on 9724 unique movies

Lastly, let’s randomize our data and then create our feature and response tensors. Note that our feature set simply contains the user and movie ID.

set.seed(123)
movie_data <- movie_data %>% sample_frac()

x_train <- movie_data %>% select(c(user_id, dense_movie_id)) %>% as.matrix()
#y_train <- movie_data %>% select(rating) %>% as.matrix()
y_train <- movie_data %>% pull(rating)

head(x_train)
     user_id dense_movie_id
[1,]      63           1160
[2,]     160           1414
[3,]     469             25
[4,]     474            562
[5,]     597           6169
[6,]     298           1959

Create a collaborative filtering algorithm

Collaborative filtering is a general concept and there are several algorithms to implement it. Here is a good article that discusses the different types but they can loosely be categorized as:

The following implements a neural network approach.

Embeddings

One of the first things we need to do is select the dimension of the embeddings that we will use for users and movies. As with word embeddings, the dimension of our embeddings is a tunable hyperparameter. For now, we’ll use 64.

embedding_dim <- 64

Basic model

To build our model, we need to take a different approach than the traditional keras_sequential() model. Instead we need to build a model that resembles this:

First, let’s create our input and embedding layers. We create an input and embedding for our user IDs and our movie IDs. Since each of these inputs are a single dimension we specify shape = 1 in our layer_input().

Our embedding layers build onto each of these inputs:

  • input_dim: input dimension has to be equal to the number of unique words. If zero maps to a word, one can leave input_dim = n_users otherwise input_dim = n_users + 1. Typically only relevant within Python API.
  • output_dim: represents the desired embeddings dimension (64 in this example).
# input layers
input_users <- layer_input(shape = 1, name = "users")
input_movies <- layer_input(shape = 1, name = "movies")

user_embeddings <- input_users %>% 
  layer_embedding(
    input_dim = n_users + 1,
    output_dim = embedding_dim,
    name = "user_embeddings"
  ) 

movie_embeddings <- input_movies %>% 
  layer_embedding(
    input_dim = n_movies + 1,
    output_dim = embedding_dim,
    name = "movie_embeddings"
  ) 

Recall in from our Excel example, we multiplied the user embeddings by the movie embeddings. This is referred to as a dot product and we can use layer_dot() to execute this computation. Since our embeddings outputs are matrices we want to perform a dot product with the embedding columns (axes = 2). If our outputs were vectors we would use axes = 1.

We add our final prediction layer with layer_dense(). Since our predicted rating can’t be < 0 I use activation = "relu" rather than a purely linear activation.

dot <- layer_dot(list(user_embeddings, movie_embeddings), axes = 2, name = "dot_product")

pred <- dot %>% layer_dense(units = 1, activation = "relu", name = "rating_prediction")

Now, we just need to combine these layers into a keras model. We use keras_model() to do so and we specify our 2 input layers and map them to our output layer. We can then add our compilation information as usual.

Note how our model summary illustrates how our layers are connected together.

# define model inputs/outputs
model <- keras_model(inputs = c(input_users, input_movies), outputs = pred)

model %>% compile(
  optimizer = "rmsprop",
  loss = "mse",
  metric = "mae"
)

# inspect model
summary(model)
Model: "model_2"
___________________________________________________________________________________
Layer (type)               Output Shape      Param #   Connected to                
===================================================================================
users (InputLayer)         [(None, 1)]       0                                     
___________________________________________________________________________________
movies (InputLayer)        [(None, 1)]       0                                     
___________________________________________________________________________________
user_embeddings (Embedding (None, 1, 64)     39104     users[0][0]                 
___________________________________________________________________________________
movie_embeddings (Embeddin (None, 1, 64)     622400    movies[0][0]                
___________________________________________________________________________________
dot_product (Dot)          (None, 1, 1)      0         user_embeddings[0][0]       
                                                       movie_embeddings[0][0]      
___________________________________________________________________________________
rating_prediction (Dense)  (None, 1, 1)      2         dot_product[0][0]           
===================================================================================
Total params: 661,506
Trainable params: 661,506
Non-trainable params: 0
___________________________________________________________________________________

We are now ready to train our model. The only difference in this step is since we have two different input layers (input_users & input_movies), we need to supply a list of two inputs:

  • x_train[, "user_id", drop = FALSE]: tensor (matrix) of user IDs
  • x_train[, "dense_movie_id", drop = FALSE]: tensor (matrix) of movie IDs
# train the model
history <- model %>% fit(
  x = list(
    x_train[, "user_id", drop = FALSE],
    x_train[, "dense_movie_id", drop = FALSE]
  ),
  y = y_train,
  epochs = 10,
  batch_size = 32, 
  validation_split = 0.2,
  callbacks = list(callback_early_stopping(patience = 2))
)

Our model obtains a a loss in the lower 0.8 range.

best_epoch <- which(history$metrics$val_loss == min(history$metrics$val_loss))
loss <- history$metrics$val_loss[best_epoch] %>% round(3)
mae <- history$metrics$val_mae[best_epoch] %>% round(3)

glue("The best epoch had a loss of {loss} and mean absolute error of {mae}")
The best epoch had a loss of 0.823 and mean absolute error of 0.699

Accounting for bias

Unfortunately, our simple model does not account for biases. For example, some people tend to rate everything favorably and some movies are consistently highly rated. We can capture this extra information by including extra bias weights in our model ℹ️.

Doing this results in a neural net architecture that looks like:

We follow the same procedure as before to set up the user and movie embeddings. We also create two new bias layers (user_bias & movie_bias) that will have an output dimension of 1 since this is creating a single bias weight for each user and movie.

# input layers
input_users <- layer_input(shape = 1, name = "users")
input_movies <- layer_input(shape = 1, name = "movies")

user_embeddings <- input_users %>%
  layer_embedding(
    input_dim = n_users + 1,
    output_dim = embedding_dim,
    name = "user_embeddings"
  )

movie_embeddings <- input_movies %>%
  layer_embedding(
    input_dim = n_movies + 1,
    output_dim = embedding_dim,
    name = "movie_embeddings"
  )

user_bias <- input_users %>%
  layer_embedding(
    input_dim = n_users + 1,
    output_dim = 1,
    name = "user_bias"
  ) 

movie_bias <- input_users %>%
  layer_embedding(
    input_dim = n_movies + 1,
    output_dim = 1,
    name = "movie_bias"
  ) 

We create our dot product and then add one more layer that adds the dot product with the user and movie biases (via layer_add()). We then complete our model with our final prediction layer.

dot <- layer_dot(list(user_embeddings, movie_embeddings), axes = 2, name = "dot_product") 
dot_bias <- layer_add(list(dot, user_bias, movie_bias), name = "add_bias")

pred <- dot_bias %>% layer_dense(units = 1, activation = "relu", name = "rating_prediction")

We follow the same procedure to build our model with keras_model() and then compile. Our model summary shows our new layers that include, or are connected to, our biases.

# define model inputs/outputs
model <- keras_model(inputs = c(input_users, input_movies), outputs = pred)

model %>% compile(
  optimizer = "rmsprop",
  loss = "mse",
  metric = "mae"
)

# inspect model
summary(model)
Model: "model_3"
___________________________________________________________________________________
Layer (type)               Output Shape      Param #   Connected to                
===================================================================================
users (InputLayer)         [(None, 1)]       0                                     
___________________________________________________________________________________
movies (InputLayer)        [(None, 1)]       0                                     
___________________________________________________________________________________
user_embeddings (Embedding (None, 1, 64)     39104     users[0][0]                 
___________________________________________________________________________________
movie_embeddings (Embeddin (None, 1, 64)     622400    movies[0][0]                
___________________________________________________________________________________
dot_product (Dot)          (None, 1, 1)      0         user_embeddings[0][0]       
                                                       movie_embeddings[0][0]      
___________________________________________________________________________________
user_bias (Embedding)      (None, 1, 1)      611       users[0][0]                 
___________________________________________________________________________________
movie_bias (Embedding)     (None, 1, 1)      9725      users[0][0]                 
___________________________________________________________________________________
add_bias (Add)             (None, 1, 1)      0         dot_product[0][0]           
                                                       user_bias[0][0]             
                                                       movie_bias[0][0]            
___________________________________________________________________________________
rating_prediction (Dense)  (None, 1, 1)      2         add_bias[0][0]              
===================================================================================
Total params: 671,842
Trainable params: 671,842
Non-trainable params: 0
___________________________________________________________________________________

We train our model the same way as before:

# train the model
history <- model %>% fit(
  x = list(
    x_train[, "user_id", drop = FALSE],
    x_train[, "dense_movie_id", drop = FALSE]
  ),
  y = y_train,
  epochs = 10,
  batch_size = 32, 
  validation_split = 0.2,
  callbacks = list(callback_early_stopping(patience = 2))
)

Our results show an improvement of over 5 percentage points! Spending some time on hyperparameter optimization could very well lead to even better results.

best_epoch <- which(history$metrics$val_loss == min(history$metrics$val_loss))
loss <- history$metrics$val_loss[best_epoch] %>% round(3)
mae <- history$metrics$val_mae[best_epoch] %>% round(3)

glue("The best epoch had a loss of {loss} and mean absolute error of {mae}")
The best epoch had a loss of 0.752 and mean absolute error of 0.665

A closer look at the embeddings

If we wanted to take a closer look at our beddings we can always access them. For example, let’s grab the movie embeddings:

movie_embeddings <- model %>%
  get_layer("movie_embeddings") %>% 
  get_weights() %>%
  .[[1]]

The following just adds the actual movie titles to the embeddings after some regex clean up to remote unncessary info. Note that the movie embeddings are ordered based on the dense_movie_id value (i.e. 1, 2, …, n) so we need to properly order the titles before adding them as row names.

movie_titles <- movie_data %>%
  select(dense_movie_id, title) %>%
  distinct() %>%
  arrange(dense_movie_id) %>%
  mutate(title = title %>% str_remove("\\(.+\\)") %>% str_trim())

row.names(movie_embeddings) <- c(NA, movie_titles$title)

movie_embeddings[1:10, 1:4]
                             [,1]        [,2]         [,3]          [,4]
<NA>                -4.592573e-02 -0.01919325  0.007135928  0.0019217953
Toy Story            3.643486e-03  0.09753495 -0.119345210  0.0438701920
Grumpier Old Men     9.284683e-02 -0.05907821  0.084155567 -0.0423735417
Heat                -2.757428e-02  0.12299450  0.098824248 -0.0811886936
Seven               -6.609381e-02  0.07417659 -0.027534399 -0.0506224036
Usual Suspects, The  7.286523e-02  0.12686753  0.143334478 -0.0002370931
From Dusk Till Dawn  2.566775e-03  0.05834844  0.015064334 -0.0249538459
Bottle Rocket        5.911291e-05  0.05221221  0.001492833  0.0465200990
Braveheart           8.734013e-02 -0.14984553 -0.035077292 -0.0113236960
Rob Roy              8.418966e-02 -0.01517612 -0.092005037 -0.0195364524

We can now use some kind of dimension reduction procedure. The following applies TSNe to group our movie embeddings along two dimensions and then plot them. If you zoom in you will see some clear themes among the groupings (i.e. Billy Madison, The Wedding Singer, Dumb & Dumber, Austin Powers are similar comedies).

n_words_to_plot <- 200

tsne <- Rtsne::Rtsne(
  X = movie_embeddings[1:n_words_to_plot,], 
  perplexity = 30, 
  pca = FALSE
  )

p <- tsne$Y %>%
  as.data.frame() %>%
  mutate(word = row.names(movie_embeddings)[1:n_words_to_plot]) %>%
  ggplot(aes(x = V1, y = V2, label = word)) + 
  geom_text(size = 3)

plotly::ggplotly(p)

You could do a similar process to find similar groupings of customers.

Make a customer prediction

Now that we have a model, we often want to make recommendations to customers about new products we think they’d like. For example, let’s look at customer 53. The following does some data wrangling to identify the movies that user 53 has and has not watched.

We can use this info to recommend a movie to this customer that we think they would enjoy but have not watched yet.

user_53 <- movie_data %>%
  filter(user_id == 53) %>%
  select(user_id, dense_movie_id) %>%
  as.matrix()

movies_watched <- movie_data %>%
  filter(user_id == 53) %>% 
  pull(dense_movie_id)

all_movies <- movie_data %>% 
  distinct(dense_movie_id) %>%
  pull()
  
movies_not_watched <- setdiff(all_movies, movies_watched)

movie_options <- movie_data %>%
  filter(dense_movie_id %in% movies_not_watched) %>%
  distinct(dense_movie_id, title)

movie_options

To do so, we create a new matrix that includes the user ID. In this example we this column is always “53” since we are only focusing on this one user. We then add a second column of all the dense_movie_ids for the movies that user 53 has not watched.

customer_53_options <- expand.grid(
  user_id = 53, 
  dense_movie_id = movies_not_watched
  ) %>%
  as.matrix()

head(customer_53_options)
     user_id dense_movie_id
[1,]      53           1160
[2,]      53           1414
[3,]      53             25
[4,]      53            562
[5,]      53           6169
[6,]      53           1959

We can now feed this information into our predict() function. Remember, our keras model takes two inputs (user_id & dense_movie_id) so our predict() function is going to expect a list of two inputs as well.

inputs <- list(
  customer_53_options[, "user_id", drop = FALSE],
  customer_53_options[, "dense_movie_id", drop = FALSE]
  )

pred <- model %>% predict(inputs)

head(pred)
[1] 4.721345 3.512779 3.945693 4.092127 3.771450 4.111283

We can now add these predictions to our customer_53_options data, join the movie_options dataset that has the titles for the movies and rank-order our movies for those that have the highest expected rating.

customer_53_options %>%
  as_tibble() %>%
  mutate(predictions = as.vector(pred)) %>%
  left_join(movie_options, by = "dense_movie_id") %>%
  arrange(desc(predictions))

Key takeaways

LS0tCnRpdGxlOiAiTW92aWUgcmVjb21tZW5kYXRpb25zIHdpdGggY29sbGFib3JhdGl2ZSBmaWx0ZXJpbmciCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUsIGNhY2hlID0gVFJVRSkKZ2dwbG90Mjo6dGhlbWVfc2V0KGdncGxvdDI6OnRoZW1lX2J3KCkpCmBgYAoKSW4gdGhpcyBleGFtcGxlLCB3ZSBhcmUgZ29pbmcgdG8gbGVhcm4gaG93IHRvIG1ha2UgYSByZWNvbW1lbmRhdGlvbiBzeXN0ZW0gdXNpbmcKY29sbGFib3JhdGl2ZSBmaWx0ZXJpbmcuIENvbGxhYm9yYXRpdmUgZmlsdGVyaW5nIGlzIG9uZSBvZiB0aGUgbW9zdCBjb21tb24KYXBwcm9hY2hlcyB1c2VkIHRvIHJlY29tbWVuZCBwcm9kdWN0cyBvciBzZXJ2aWNlcyB0byBjdXN0b21lcnMgYW5kIGJlY2FtZSB2ZXJ5CnBvcHVsYXIgYWZ0ZXIgdGhlIGZhbW91cyBbTmV0ZmxpeCBjb21wZXRpdGlvbl0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTmV0ZmxpeF9Qcml6ZSkuCkJ5IGNyZWF0aW5nIGEgY29sbGFib3JhdGl2ZSBmaWx0ZXJpbmcgYWxnb3JpdGhtIHdpdGgga2VyYXMsIHlvdSB3aWxsIGFsc28gYmUKZXhwb3NlZCB0byBob3cgd2UgY2FuIGNyZWF0ZSBtb3JlIGN1c3RvbWl6ZWQgbW9kZWxzIHdpdGgga2VyYXMnIGZ1bmN0aW9uYWwKbW9kZWwgb3B0aW9ucy4KCkxlYXJuaW5nIG9iamVjdGl2ZXM6CgotIEhvdyB0byBjcmVhdGUgYSBuZXVyYWwgbmV0d29yayBjb2xsYWJvcmF0aXZlIGZpbHRlcmluZyBhbGdvcml0aG0KLSBIb3cgdG8gY3JlYXRlIGEgY3VzdG9taXplZCBmdW5jdGlvbmFsIGtlcmFzIG1vZGVsCgojIFJlcXVpcmVtZW50cwoKYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoa2VyYXMpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGdsdWUpCmBgYAoKIyBQcmVwYXJlIG91ciBkYXRhCgpGb3IgdGhpcyBtb2R1bGUgd2UnbGwgdXNlIFtNb3ZpZUxlbnMgZGF0YV0oaHR0cHM6Ly9ncm91cGxlbnMub3JnL2RhdGFzZXRzL21vdmllbGVucy8pLAp3aGljaCBwcm92aWRlcyB1c2VyIHJhdGluZyBpbmZvcm1hdGlvbiBmb3IgbW92aWVzLiBUaGVyZSBhcmUgbXVsdGlwbGUgZGF0YXNldApzaXplczsgaG93ZXZlciwgZm9yIGVmZmljaWVuY3kgd2Ugd2lsbCB1c2UgdGhlIHNtYWxsZXIgZGF0YXNldCB0aGF0IGNvbnRhaW5zCjEwMCw4MzYgcmF0aW5ncyBvZiA5LDcyNCBtb3ZpZXMgcmF0ZWQgYnkgNjEwIHVzZXJzLgoKYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmRhdGFfZGlyIDwtIGhlcmU6OmhlcmUoIm1hdGVyaWFscyIsICJkYXRhIiwgIm1sLWxhdGVzdC1zbWFsbCIpCm1vdmllcyA8LSByZWFkX2NzdihmaWxlLnBhdGgoZGF0YV9kaXIsICJtb3ZpZXMuY3N2IikpCnJhdGluZ3MgPC0gcmVhZF9jc3YoZmlsZS5wYXRoKGRhdGFfZGlyLCAicmF0aW5ncy5jc3YiKSkKYGBgCgpDdXJyZW50bHkgb3VyIGRhdGFzZXRzIGFyZSBzZXBhcmF0ZSBhbmQgbW92aWUgSUQgcmFuZ2VzIGZyb20gMSB0byAxOTMsNjA5IGV2ZW4KdGhvdWdoIG91ciBkYXRhIG9ubHkgY29udGFpbnMgOSw3MjQgdW5pcXVlIG1vdmllIElEcy4gQ29uc2VxdWVudGx5LCB0aGUgZm9sbG93aW5nCmNyZWF0ZXMgYSBgZGVuc2VfbW92aWVfaWRgIHNvIHRoZXJlIGFyZSBubyBnYXBzLCB3aGljaCBtYWtlcyBmdXR1cmUgbWFwcGluZyBvZgpvdXIgd29yZCB2ZWN0b3IgdG8gZW1iZWRkaW5ncyBzaW1wbGVyLCBhbmQgYWxzbyBqb2lucyBvdXIgZGF0YXNldHMgYW5kCmNsZWFucyB1cCBvdXIgY29sdW1uIG5hbWVzLgoKYGBge3IsIG1lc3NhZ2U9RkFMU0V9Cm1vdmllX2RhdGEgPC0gcmF0aW5ncyAlPiUgCiAgZGlzdGluY3QobW92aWVJZCkgJT4lCiAgcm93aWRfdG9fY29sdW1uKHZhciA9ICJkZW5zZV9tb3ZpZV9pZCIpICU+JQogIGlubmVyX2pvaW4ocmF0aW5ncykgJT4lCiAgaW5uZXJfam9pbihtb3ZpZXMpICU+JQogIHNlbGVjdCh1c2VyX2lkID0gdXNlcklkLCBtb3ZpZV9pZCA9IG1vdmllSWQsIGRlbnNlX21vdmllX2lkLCByYXRpbmcsIGV2ZXJ5dGhpbmcoKSkKCm1vdmllX2RhdGEKYGBgCgpMZXQncyBleHRyYWN0IHRoZSBudW1iZXIgb2YgbW92aWVzIGFuZCB1c2Vycy4gV2UnbGwgdXNlIHRoZXNlIHBhcmFtZXRlcnMgbGF0ZXIKaW4gb3VyIGtlcmFzIG1vZGVsLgoKYGBge3J9Cm5fbW92aWVzIDwtIG5fZGlzdGluY3QobW92aWVfZGF0YSRkZW5zZV9tb3ZpZV9pZCkKbl91c2VycyA8LSBuX2Rpc3RpbmN0KG1vdmllX2RhdGEkdXNlcl9pZCkKCmdsdWUoIlRoaXMgZGF0YXNldCBpbmNsdWRlcyB7bnJvdyhtb3ZpZV9kYXRhKX0gcmF0aW5ncyBieSB7bl91c2Vyc30gdXNlcnMgb24ge25fbW92aWVzfSB1bmlxdWUgbW92aWVzIikKYGBgCgpMYXN0bHksIGxldCdzIHJhbmRvbWl6ZSBvdXIgZGF0YSBhbmQgdGhlbiBjcmVhdGUgb3VyIGZlYXR1cmUgYW5kIHJlc3BvbnNlCnRlbnNvcnMuIE5vdGUgdGhhdCBvdXIgZmVhdHVyZSBzZXQgc2ltcGx5IGNvbnRhaW5zIHRoZSB1c2VyIGFuZCBtb3ZpZSBJRC4KCmBgYHtyfQpzZXQuc2VlZCgxMjMpCm1vdmllX2RhdGEgPC0gbW92aWVfZGF0YSAlPiUgc2FtcGxlX2ZyYWMoKQoKeF90cmFpbiA8LSBtb3ZpZV9kYXRhICU+JSBzZWxlY3QoYyh1c2VyX2lkLCBkZW5zZV9tb3ZpZV9pZCkpICU+JSBhcy5tYXRyaXgoKQp5X3RyYWluIDwtIG1vdmllX2RhdGEgJT4lIHB1bGwocmF0aW5nKQoKaGVhZCh4X3RyYWluKQpgYGAKCiMgQ3JlYXRlIGEgY29sbGFib3JhdGl2ZSBmaWx0ZXJpbmcgYWxnb3JpdGhtCgpDb2xsYWJvcmF0aXZlIGZpbHRlcmluZyBpcyBhIGdlbmVyYWwgY29uY2VwdCBhbmQgdGhlcmUgYXJlIHNldmVyYWwgYWxnb3JpdGhtcyB0bwppbXBsZW1lbnQgaXQuIEhlcmUgaXMgYSBnb29kIFthcnRpY2xlXShodHRwczovL2JpdC5seS8zNHNRVjhnKSB0aGF0IGRpc2N1c3Nlcwp0aGUgZGlmZmVyZW50IHR5cGVzIGJ1dCB0aGV5IGNhbiBsb29zZWx5IGJlIGNhdGVnb3JpemVkIGFzOgoKKiBEaXN0YW5jZS1iYXNlZCAoaS5lLiBjb3NpbmUgc2ltaWxhcml0eSwgY29ycmVsYXRpb24pCiogTWF0cml4IGZhY3Rvcml6YXRpb24gKFvihLnvuI9dKGh0dHA6Ly9iaXQubHkvZGwtMDctRXhjZWwpKQoqIENsdXN0ZXJpbmcKKiBEZWVwIGxlYXJuaW5nCgpUaGUgZm9sbG93aW5nIGltcGxlbWVudHMgYSBuZXVyYWwgbmV0d29yayBhcHByb2FjaC4KCiMjIEVtYmVkZGluZ3MKCk9uZSBvZiB0aGUgZmlyc3QgdGhpbmdzIHdlIG5lZWQgdG8gZG8gaXMgc2VsZWN0IHRoZSBkaW1lbnNpb24gb2YgdGhlIGVtYmVkZGluZ3MKdGhhdCB3ZSB3aWxsIHVzZSBmb3IgdXNlcnMgYW5kIG1vdmllcy4gQXMgd2l0aCB3b3JkIGVtYmVkZGluZ3MsIHRoZSBkaW1lbnNpb24gb2YKb3VyIGVtYmVkZGluZ3MgaXMgYSB0dW5hYmxlIGh5cGVycGFyYW1ldGVyLiBGb3Igbm93LCB3ZSdsbCB1c2UgNjQuCgpgYGB7cn0KZW1iZWRkaW5nX2RpbSA8LSA2NApgYGAKCiMjIEJhc2ljIG1vZGVsCgpUbyBidWlsZCBvdXIgbW9kZWwsIHdlIG5lZWQgdG8gdGFrZSBhIGRpZmZlcmVudCBhcHByb2FjaCB0aGFuIHRoZSB0cmFkaXRpb25hbApga2VyYXNfc2VxdWVudGlhbCgpYCBtb2RlbC4gSW5zdGVhZCB3ZSBuZWVkIHRvIGJ1aWxkIGEgbW9kZWwgdGhhdCByZXNlbWJsZXMgdGhpczoKCmBgYHtyLCBlY2hvPUZBTFNFLCBmaWcuYWxpZ249J2NlbnRlcid9CmtuaXRyOjppbmNsdWRlX2dyYXBoaWNzKCJpbWFnZXMvY29sbGFib3JhdGl2ZS1maWx0ZXJpbmcta2VyYXMtbW9kZWwucG5nIikKYGBgCgpGaXJzdCwgbGV0J3MgY3JlYXRlIG91ciBpbnB1dCBhbmQgZW1iZWRkaW5nIGxheWVycy4gV2UgY3JlYXRlIGFuIGlucHV0IGFuZAplbWJlZGRpbmcgZm9yIG91ciB1c2VyIElEcyBhbmQgb3VyIG1vdmllIElEcy4gU2luY2UgZWFjaCBvZiB0aGVzZSBpbnB1dHMgYXJlIGEKc2luZ2xlIGRpbWVuc2lvbiB3ZSBzcGVjaWZ5IGBzaGFwZSA9IDFgIGluIG91ciBgbGF5ZXJfaW5wdXQoKWAuCgpPdXIgZW1iZWRkaW5nIGxheWVycyBidWlsZCBvbnRvIGVhY2ggb2YgdGhlc2UgaW5wdXRzOgoKLSBgaW5wdXRfZGltYDogaW5wdXQgZGltZW5zaW9uIGhhcyB0byBiZSBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIHVuaXF1ZSB3b3Jkcy4KICAgSWYgemVybyBtYXBzIHRvIGEgd29yZCwgb25lIGNhbiBsZWF2ZSBgaW5wdXRfZGltID0gbl91c2Vyc2AgIG90aGVyd2lzZQogICBgaW5wdXRfZGltID0gbl91c2VycyArIDFgLiBUeXBpY2FsbHkgb25seSByZWxldmFudCB3aXRoaW4gUHl0aG9uIEFQSS4KLSBgb3V0cHV0X2RpbWA6IHJlcHJlc2VudHMgdGhlIGRlc2lyZWQgZW1iZWRkaW5ncyBkaW1lbnNpb24gKDY0IGluIHRoaXMgZXhhbXBsZSkuCgpgYGB7cn0KIyBpbnB1dCBsYXllcnMKaW5wdXRfdXNlcnMgPC0gbGF5ZXJfaW5wdXQoc2hhcGUgPSAxLCBuYW1lID0gInVzZXJzIikKaW5wdXRfbW92aWVzIDwtIGxheWVyX2lucHV0KHNoYXBlID0gMSwgbmFtZSA9ICJtb3ZpZXMiKQoKdXNlcl9lbWJlZGRpbmdzIDwtIGlucHV0X3VzZXJzICU+JSAKICBsYXllcl9lbWJlZGRpbmcoCiAgICBpbnB1dF9kaW0gPSBuX3VzZXJzICsgMSwKICAgIG91dHB1dF9kaW0gPSBlbWJlZGRpbmdfZGltLAogICAgbmFtZSA9ICJ1c2VyX2VtYmVkZGluZ3MiCiAgKSAKCm1vdmllX2VtYmVkZGluZ3MgPC0gaW5wdXRfbW92aWVzICU+JSAKICBsYXllcl9lbWJlZGRpbmcoCiAgICBpbnB1dF9kaW0gPSBuX21vdmllcyArIDEsCiAgICBvdXRwdXRfZGltID0gZW1iZWRkaW5nX2RpbSwKICAgIG5hbWUgPSAibW92aWVfZW1iZWRkaW5ncyIKICApIApgYGAKClJlY2FsbCBpbiBmcm9tIG91ciBFeGNlbCBleGFtcGxlLCB3ZSBtdWx0aXBsaWVkIHRoZSB1c2VyIGVtYmVkZGluZ3MgYnkgdGhlIG1vdmllCmVtYmVkZGluZ3MuIFRoaXMgaXMgcmVmZXJyZWQgdG8gYXMgYSBkb3QgcHJvZHVjdCBhbmQgd2UgY2FuIHVzZSBgbGF5ZXJfZG90KClgIHRvCmV4ZWN1dGUgdGhpcyBjb21wdXRhdGlvbi4gU2luY2Ugb3VyIGVtYmVkZGluZ3Mgb3V0cHV0cyBhcmUgbWF0cmljZXMgd2Ugd2FudCB0bwpwZXJmb3JtIGEgZG90IHByb2R1Y3Qgd2l0aCB0aGUgZW1iZWRkaW5nIGNvbHVtbnMgKGBheGVzID0gMmApLiBJZiBvdXIgb3V0cHV0cwp3ZXJlIHZlY3RvcnMgd2Ugd291bGQgdXNlIGBheGVzID0gMWAuCgpXZSBhZGQgb3VyIGZpbmFsIHByZWRpY3Rpb24gbGF5ZXIgd2l0aCBgbGF5ZXJfZGVuc2UoKWAuIFNpbmNlIG91ciBwcmVkaWN0ZWQKcmF0aW5nIGNhbid0IGJlIDwgMCBJIHVzZSBgYWN0aXZhdGlvbiA9ICJyZWx1ImAgcmF0aGVyIHRoYW4gYSBwdXJlbHkgbGluZWFyCmFjdGl2YXRpb24uCgpgYGB7cn0KZG90IDwtIGxheWVyX2RvdChsaXN0KHVzZXJfZW1iZWRkaW5ncywgbW92aWVfZW1iZWRkaW5ncyksIGF4ZXMgPSAyLCBuYW1lID0gImRvdF9wcm9kdWN0IikKCnByZWQgPC0gZG90ICU+JSBsYXllcl9kZW5zZSh1bml0cyA9IDEsIGFjdGl2YXRpb24gPSAicmVsdSIsIG5hbWUgPSAicmF0aW5nX3ByZWRpY3Rpb24iKQpgYGAKCk5vdywgd2UganVzdCBuZWVkIHRvIGNvbWJpbmUgdGhlc2UgbGF5ZXJzIGludG8gYSBrZXJhcyBtb2RlbC4gV2UgdXNlCmBrZXJhc19tb2RlbCgpYCB0byBkbyBzbyBhbmQgd2Ugc3BlY2lmeSBvdXIgMiBpbnB1dCBsYXllcnMgYW5kIG1hcCB0aGVtIHRvIG91cgpvdXRwdXQgbGF5ZXIuIFdlIGNhbiB0aGVuIGFkZCBvdXIgY29tcGlsYXRpb24gaW5mb3JtYXRpb24gYXMgdXN1YWwuCgpOb3RlIGhvdyBvdXIgbW9kZWwgc3VtbWFyeSBpbGx1c3RyYXRlcyBob3cgb3VyIGxheWVycyBhcmUgY29ubmVjdGVkIHRvZ2V0aGVyLgoKYGBge3J9CiMgZGVmaW5lIG1vZGVsIGlucHV0cy9vdXRwdXRzCm1vZGVsIDwtIGtlcmFzX21vZGVsKGlucHV0cyA9IGMoaW5wdXRfdXNlcnMsIGlucHV0X21vdmllcyksIG91dHB1dHMgPSBwcmVkKQoKbW9kZWwgJT4lIGNvbXBpbGUoCiAgb3B0aW1pemVyID0gInJtc3Byb3AiLAogIGxvc3MgPSAibXNlIiwKICBtZXRyaWMgPSAibWFlIgopCgojIGluc3BlY3QgbW9kZWwKc3VtbWFyeShtb2RlbCkKYGBgCgpXZSBhcmUgbm93IHJlYWR5IHRvIHRyYWluIG91ciBtb2RlbC4gVGhlIG9ubHkgZGlmZmVyZW5jZSBpbiB0aGlzIHN0ZXAgaXMgc2luY2UKd2UgaGF2ZSB0d28gZGlmZmVyZW50IGlucHV0IGxheWVycyAoYGlucHV0X3VzZXJzYCAmIGBpbnB1dF9tb3ZpZXNgKSwgd2UgbmVlZCB0bwpzdXBwbHkgYSBsaXN0IG9mIHR3byBpbnB1dHM6CgotIGB4X3RyYWluWywgInVzZXJfaWQiLCBkcm9wID0gRkFMU0VdYDogdGVuc29yIChtYXRyaXgpIG9mIHVzZXIgSURzCi0gYHhfdHJhaW5bLCAiZGVuc2VfbW92aWVfaWQiLCBkcm9wID0gRkFMU0VdYDogdGVuc29yIChtYXRyaXgpIG9mIG1vdmllIElEcwoKYGBge3J9CiMgdHJhaW4gdGhlIG1vZGVsCmhpc3RvcnkgPC0gbW9kZWwgJT4lIGZpdCgKICB4ID0gbGlzdCgKICAgIHhfdHJhaW5bLCAidXNlcl9pZCIsIGRyb3AgPSBGQUxTRV0sCiAgICB4X3RyYWluWywgImRlbnNlX21vdmllX2lkIiwgZHJvcCA9IEZBTFNFXQogICksCiAgeSA9IHlfdHJhaW4sCiAgZXBvY2hzID0gMTAsCiAgYmF0Y2hfc2l6ZSA9IDMyLCAKICB2YWxpZGF0aW9uX3NwbGl0ID0gMC4yLAogIGNhbGxiYWNrcyA9IGxpc3QoY2FsbGJhY2tfZWFybHlfc3RvcHBpbmcocGF0aWVuY2UgPSAyKSkKKQpgYGAKCk91ciBtb2RlbCBvYnRhaW5zIGEgYSBsb3NzIGluIHRoZSBsb3dlciAwLjggcmFuZ2UuCgpgYGB7cn0KYmVzdF9lcG9jaCA8LSB3aGljaChoaXN0b3J5JG1ldHJpY3MkdmFsX2xvc3MgPT0gbWluKGhpc3RvcnkkbWV0cmljcyR2YWxfbG9zcykpCmxvc3MgPC0gaGlzdG9yeSRtZXRyaWNzJHZhbF9sb3NzW2Jlc3RfZXBvY2hdICU+JSByb3VuZCgzKQptYWUgPC0gaGlzdG9yeSRtZXRyaWNzJHZhbF9tYWVbYmVzdF9lcG9jaF0gJT4lIHJvdW5kKDMpCgpnbHVlKCJUaGUgYmVzdCBlcG9jaCBoYWQgYSBsb3NzIG9mIHtsb3NzfSBhbmQgbWVhbiBhYnNvbHV0ZSBlcnJvciBvZiB7bWFlfSIpCmBgYAoKIyMgQWNjb3VudGluZyBmb3IgYmlhcwoKVW5mb3J0dW5hdGVseSwgb3VyIHNpbXBsZSBtb2RlbCBkb2VzIG5vdCBhY2NvdW50IGZvciBiaWFzZXMuIEZvciBleGFtcGxlLCBzb21lCnBlb3BsZSB0ZW5kIHRvIHJhdGUgZXZlcnl0aGluZyBmYXZvcmFibHkgYW5kIHNvbWUgbW92aWVzIGFyZSBjb25zaXN0ZW50bHkgaGlnaGx5CnJhdGVkLiBXZSBjYW4gY2FwdHVyZSB0aGlzIGV4dHJhIGluZm9ybWF0aW9uIGJ5IGluY2x1ZGluZyBleHRyYSBiaWFzIHdlaWdodHMgaW4Kb3VyIG1vZGVsIFvihLnvuI9dKGh0dHA6Ly9iaXQubHkvZGwtMDctRXhjZWwpLgoKRG9pbmcgdGhpcyByZXN1bHRzIGluIGEgbmV1cmFsIG5ldCBhcmNoaXRlY3R1cmUgdGhhdCBsb29rcyBsaWtlOgoKYGBge3IsIGVjaG89RkFMU0UsIGZpZy5hbGlnbj0nY2VudGVyJ30Ka25pdHI6OmluY2x1ZGVfZ3JhcGhpY3MoImltYWdlcy9jb2xsYWJvcmF0aXZlLWZpbHRlcmluZy1rZXJhcy1tb2RlbDIucG5nIikKYGBgCgpXZSBmb2xsb3cgdGhlIHNhbWUgcHJvY2VkdXJlIGFzIGJlZm9yZSB0byBzZXQgdXAgdGhlIHVzZXIgYW5kIG1vdmllIGVtYmVkZGluZ3MuCldlIGFsc28gY3JlYXRlIHR3byBuZXcgYmlhcyBsYXllcnMgKGB1c2VyX2JpYXNgICYgYG1vdmllX2JpYXNgKSB0aGF0IHdpbGwgaGF2ZQphbiBvdXRwdXQgZGltZW5zaW9uIG9mIDEgc2luY2UgdGhpcyBpcyBjcmVhdGluZyBhIHNpbmdsZSBiaWFzIHdlaWdodCBmb3IgZWFjaAp1c2VyIGFuZCBtb3ZpZS4KCmBgYHtyfQojIGlucHV0IGxheWVycwppbnB1dF91c2VycyA8LSBsYXllcl9pbnB1dChzaGFwZSA9IDEsIG5hbWUgPSAidXNlcnMiKQppbnB1dF9tb3ZpZXMgPC0gbGF5ZXJfaW5wdXQoc2hhcGUgPSAxLCBuYW1lID0gIm1vdmllcyIpCgp1c2VyX2VtYmVkZGluZ3MgPC0gaW5wdXRfdXNlcnMgJT4lCiAgbGF5ZXJfZW1iZWRkaW5nKAogICAgaW5wdXRfZGltID0gbl91c2VycyArIDEsCiAgICBvdXRwdXRfZGltID0gZW1iZWRkaW5nX2RpbSwKICAgIG5hbWUgPSAidXNlcl9lbWJlZGRpbmdzIgogICkKCm1vdmllX2VtYmVkZGluZ3MgPC0gaW5wdXRfbW92aWVzICU+JQogIGxheWVyX2VtYmVkZGluZygKICAgIGlucHV0X2RpbSA9IG5fbW92aWVzICsgMSwKICAgIG91dHB1dF9kaW0gPSBlbWJlZGRpbmdfZGltLAogICAgbmFtZSA9ICJtb3ZpZV9lbWJlZGRpbmdzIgogICkKCnVzZXJfYmlhcyA8LSBpbnB1dF91c2VycyAlPiUKICBsYXllcl9lbWJlZGRpbmcoCiAgICBpbnB1dF9kaW0gPSBuX3VzZXJzICsgMSwKICAgIG91dHB1dF9kaW0gPSAxLAogICAgbmFtZSA9ICJ1c2VyX2JpYXMiCiAgKSAKCm1vdmllX2JpYXMgPC0gaW5wdXRfdXNlcnMgJT4lCiAgbGF5ZXJfZW1iZWRkaW5nKAogICAgaW5wdXRfZGltID0gbl9tb3ZpZXMgKyAxLAogICAgb3V0cHV0X2RpbSA9IDEsCiAgICBuYW1lID0gIm1vdmllX2JpYXMiCiAgKSAKYGBgCgpXZSBjcmVhdGUgb3VyIGRvdCBwcm9kdWN0IGFuZCB0aGVuIGFkZCBvbmUgbW9yZSBsYXllciB0aGF0IGFkZHMgdGhlIGRvdCBwcm9kdWN0CndpdGggdGhlIHVzZXIgYW5kIG1vdmllIGJpYXNlcyAodmlhIGBsYXllcl9hZGQoKWApLiBXZSB0aGVuIGNvbXBsZXRlIG91ciBtb2RlbAp3aXRoIG91ciBmaW5hbCBwcmVkaWN0aW9uIGxheWVyLgoKYGBge3J9CmRvdCA8LSBsYXllcl9kb3QobGlzdCh1c2VyX2VtYmVkZGluZ3MsIG1vdmllX2VtYmVkZGluZ3MpLCBheGVzID0gMiwgbmFtZSA9ICJkb3RfcHJvZHVjdCIpIApkb3RfYmlhcyA8LSBsYXllcl9hZGQobGlzdChkb3QsIHVzZXJfYmlhcywgbW92aWVfYmlhcyksIG5hbWUgPSAiYWRkX2JpYXMiKQoKcHJlZCA8LSBkb3RfYmlhcyAlPiUgbGF5ZXJfZGVuc2UodW5pdHMgPSAxLCBhY3RpdmF0aW9uID0gInJlbHUiLCBuYW1lID0gInJhdGluZ19wcmVkaWN0aW9uIikKYGBgCgpXZSBmb2xsb3cgdGhlIHNhbWUgcHJvY2VkdXJlIHRvIGJ1aWxkIG91ciBtb2RlbCB3aXRoIGBrZXJhc19tb2RlbCgpYCBhbmQgdGhlbgpjb21waWxlLiBPdXIgbW9kZWwgc3VtbWFyeSBzaG93cyBvdXIgbmV3IGxheWVycyB0aGF0IGluY2x1ZGUsIG9yIGFyZSBjb25uZWN0ZWQKdG8sIG91ciBiaWFzZXMuCgpgYGB7cn0KIyBkZWZpbmUgbW9kZWwgaW5wdXRzL291dHB1dHMKbW9kZWwgPC0ga2VyYXNfbW9kZWwoaW5wdXRzID0gYyhpbnB1dF91c2VycywgaW5wdXRfbW92aWVzKSwgb3V0cHV0cyA9IHByZWQpCgptb2RlbCAlPiUgY29tcGlsZSgKICBvcHRpbWl6ZXIgPSAicm1zcHJvcCIsCiAgbG9zcyA9ICJtc2UiLAogIG1ldHJpYyA9ICJtYWUiCikKCiMgaW5zcGVjdCBtb2RlbApzdW1tYXJ5KG1vZGVsKQpgYGAKCldlIHRyYWluIG91ciBtb2RlbCB0aGUgc2FtZSB3YXkgYXMgYmVmb3JlOgoKYGBge3J9CiMgdHJhaW4gdGhlIG1vZGVsCmhpc3RvcnkgPC0gbW9kZWwgJT4lIGZpdCgKICB4ID0gbGlzdCgKICAgIHhfdHJhaW5bLCAidXNlcl9pZCIsIGRyb3AgPSBGQUxTRV0sCiAgICB4X3RyYWluWywgImRlbnNlX21vdmllX2lkIiwgZHJvcCA9IEZBTFNFXQogICksCiAgeSA9IHlfdHJhaW4sCiAgZXBvY2hzID0gMTAsCiAgYmF0Y2hfc2l6ZSA9IDMyLCAKICB2YWxpZGF0aW9uX3NwbGl0ID0gMC4yLAogIGNhbGxiYWNrcyA9IGxpc3QoY2FsbGJhY2tfZWFybHlfc3RvcHBpbmcocGF0aWVuY2UgPSAyKSkKKQpgYGAKCk91ciByZXN1bHRzIHNob3cgYW4gaW1wcm92ZW1lbnQgb2Ygb3ZlciA1IHBlcmNlbnRhZ2UgcG9pbnRzISBTcGVuZGluZyBzb21lIHRpbWUKb24gaHlwZXJwYXJhbWV0ZXIgb3B0aW1pemF0aW9uIGNvdWxkIHZlcnkgd2VsbCBsZWFkIHRvIGV2ZW4gYmV0dGVyIHJlc3VsdHMuCgpgYGB7cn0KYmVzdF9lcG9jaCA8LSB3aGljaChoaXN0b3J5JG1ldHJpY3MkdmFsX2xvc3MgPT0gbWluKGhpc3RvcnkkbWV0cmljcyR2YWxfbG9zcykpCmxvc3MgPC0gaGlzdG9yeSRtZXRyaWNzJHZhbF9sb3NzW2Jlc3RfZXBvY2hdICU+JSByb3VuZCgzKQptYWUgPC0gaGlzdG9yeSRtZXRyaWNzJHZhbF9tYWVbYmVzdF9lcG9jaF0gJT4lIHJvdW5kKDMpCgpnbHVlKCJUaGUgYmVzdCBlcG9jaCBoYWQgYSBsb3NzIG9mIHtsb3NzfSBhbmQgbWVhbiBhYnNvbHV0ZSBlcnJvciBvZiB7bWFlfSIpCmBgYAoKIyBBIGNsb3NlciBsb29rIGF0IHRoZSBlbWJlZGRpbmdzCgpJZiB3ZSB3YW50ZWQgdG8gdGFrZSBhIGNsb3NlciBsb29rIGF0IG91ciBiZWRkaW5ncyB3ZSBjYW4gYWx3YXlzIGFjY2VzcyB0aGVtLgpGb3IgZXhhbXBsZSwgbGV0J3MgZ3JhYiB0aGUgbW92aWUgZW1iZWRkaW5nczoKCmBgYHtyfQptb3ZpZV9lbWJlZGRpbmdzIDwtIG1vZGVsICU+JQogIGdldF9sYXllcigibW92aWVfZW1iZWRkaW5ncyIpICU+JSAKICBnZXRfd2VpZ2h0cygpICU+JQogIC5bWzFdXQpgYGAKClRoZSBmb2xsb3dpbmcganVzdCBhZGRzIHRoZSBhY3R1YWwgbW92aWUgdGl0bGVzIHRvIHRoZSBlbWJlZGRpbmdzIGFmdGVyIHNvbWUKcmVnZXggY2xlYW4gdXAgdG8gcmVtb3RlIHVubmNlc3NhcnkgaW5mby4gTm90ZSB0aGF0IHRoZSBtb3ZpZSBlbWJlZGRpbmdzIGFyZQpvcmRlcmVkIGJhc2VkIG9uIHRoZSBgZGVuc2VfbW92aWVfaWRgIHZhbHVlIChpLmUuIDEsIDIsIC4uLiwgbikgc28gd2UgbmVlZCB0bwpwcm9wZXJseSBvcmRlciB0aGUgdGl0bGVzIGJlZm9yZSBhZGRpbmcgdGhlbSBhcyByb3cgbmFtZXMuCgpgYGB7cn0KbW92aWVfdGl0bGVzIDwtIG1vdmllX2RhdGEgJT4lCiAgc2VsZWN0KGRlbnNlX21vdmllX2lkLCB0aXRsZSkgJT4lCiAgZGlzdGluY3QoKSAlPiUKICBhcnJhbmdlKGRlbnNlX21vdmllX2lkKSAlPiUKICBtdXRhdGUodGl0bGUgPSB0aXRsZSAlPiUgc3RyX3JlbW92ZSgiXFwoLitcXCkiKSAlPiUgc3RyX3RyaW0oKSkKCnJvdy5uYW1lcyhtb3ZpZV9lbWJlZGRpbmdzKSA8LSBjKE5BLCBtb3ZpZV90aXRsZXMkdGl0bGUpCgptb3ZpZV9lbWJlZGRpbmdzWzE6MTAsIDE6NF0KYGBgCgpXZSBjYW4gbm93IHVzZSBzb21lIGtpbmQgb2YgZGltZW5zaW9uIHJlZHVjdGlvbiBwcm9jZWR1cmUuIFRoZSBmb2xsb3dpbmcgYXBwbGllcwpUU05lIHRvIGdyb3VwIG91ciBtb3ZpZSBlbWJlZGRpbmdzIGFsb25nIHR3byBkaW1lbnNpb25zIGFuZCB0aGVuIHBsb3QgdGhlbS4gSWYKeW91IHpvb20gaW4geW91IHdpbGwgc2VlIHNvbWUgY2xlYXIgdGhlbWVzIGFtb25nIHRoZSBncm91cGluZ3MgKGkuZS4gQmlsbHkKTWFkaXNvbiwgVGhlIFdlZGRpbmcgU2luZ2VyLCBEdW1iICYgRHVtYmVyLCBBdXN0aW4gUG93ZXJzIGFyZSBzaW1pbGFyIGNvbWVkaWVzKS4KCmBgYHtyLCBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9Nn0Kbl93b3Jkc190b19wbG90IDwtIDIwMAoKdHNuZSA8LSBSdHNuZTo6UnRzbmUoCiAgWCA9IG1vdmllX2VtYmVkZGluZ3NbMTpuX3dvcmRzX3RvX3Bsb3QsXSwgCiAgcGVycGxleGl0eSA9IDMwLCAKICBwY2EgPSBGQUxTRQogICkKCnAgPC0gdHNuZSRZICU+JQogIGFzLmRhdGEuZnJhbWUoKSAlPiUKICBtdXRhdGUod29yZCA9IHJvdy5uYW1lcyhtb3ZpZV9lbWJlZGRpbmdzKVsxOm5fd29yZHNfdG9fcGxvdF0pICU+JQogIGdncGxvdChhZXMoeCA9IFYxLCB5ID0gVjIsIGxhYmVsID0gd29yZCkpICsgCiAgZ2VvbV90ZXh0KHNpemUgPSAzKQoKcGxvdGx5OjpnZ3Bsb3RseShwKQpgYGAKCllvdSBjb3VsZCBkbyBhIHNpbWlsYXIgcHJvY2VzcyB0byBmaW5kIHNpbWlsYXIgZ3JvdXBpbmdzIG9mIGN1c3RvbWVycy4KCiMgTWFrZSBhIGN1c3RvbWVyIHByZWRpY3Rpb24KCk5vdyB0aGF0IHdlIGhhdmUgYSBtb2RlbCwgd2Ugb2Z0ZW4gd2FudCB0byBtYWtlIHJlY29tbWVuZGF0aW9ucyB0byBjdXN0b21lcnMKYWJvdXQgbmV3IHByb2R1Y3RzIHdlIHRoaW5rIHRoZXknZCBsaWtlLiBGb3IgZXhhbXBsZSwgbGV0J3MgbG9vayBhdCBjdXN0b21lciA1My4KVGhlIGZvbGxvd2luZyBkb2VzIHNvbWUgZGF0YSB3cmFuZ2xpbmcgdG8gaWRlbnRpZnkgdGhlIG1vdmllcyB0aGF0IHVzZXIgNTMgaGFzCmFuZCBoYXMgbm90IHdhdGNoZWQuIAoKV2UgY2FuIHVzZSB0aGlzIGluZm8gdG8gcmVjb21tZW5kIGEgbW92aWUgdG8gdGhpcyBjdXN0b21lcgp0aGF0IHdlIHRoaW5rIHRoZXkgd291bGQgZW5qb3kgYnV0IGhhdmUgbm90IHdhdGNoZWQgeWV0LgoKYGBge3J9CnVzZXJfNTMgPC0gbW92aWVfZGF0YSAlPiUKICBmaWx0ZXIodXNlcl9pZCA9PSA1MykgJT4lCiAgc2VsZWN0KHVzZXJfaWQsIGRlbnNlX21vdmllX2lkKSAlPiUKICBhcy5tYXRyaXgoKQoKbW92aWVzX3dhdGNoZWQgPC0gbW92aWVfZGF0YSAlPiUKICBmaWx0ZXIodXNlcl9pZCA9PSA1MykgJT4lIAogIHB1bGwoZGVuc2VfbW92aWVfaWQpCgphbGxfbW92aWVzIDwtIG1vdmllX2RhdGEgJT4lIAogIGRpc3RpbmN0KGRlbnNlX21vdmllX2lkKSAlPiUKICBwdWxsKCkKICAKbW92aWVzX25vdF93YXRjaGVkIDwtIHNldGRpZmYoYWxsX21vdmllcywgbW92aWVzX3dhdGNoZWQpCgptb3ZpZV9vcHRpb25zIDwtIG1vdmllX2RhdGEgJT4lCiAgZmlsdGVyKGRlbnNlX21vdmllX2lkICVpbiUgbW92aWVzX25vdF93YXRjaGVkKSAlPiUKICBkaXN0aW5jdChkZW5zZV9tb3ZpZV9pZCwgdGl0bGUpCgptb3ZpZV9vcHRpb25zCmBgYAoKVG8gZG8gc28sIHdlIGNyZWF0ZSBhIG5ldyBtYXRyaXggdGhhdCBpbmNsdWRlcyB0aGUgdXNlciBJRC4gSW4gdGhpcyBleGFtcGxlIHdlCnRoaXMgY29sdW1uIGlzIGFsd2F5cyAiNTMiIHNpbmNlIHdlIGFyZSBvbmx5IGZvY3VzaW5nIG9uIHRoaXMgb25lIHVzZXIuIFdlIHRoZW4KYWRkIGEgc2Vjb25kIGNvbHVtbiBvZiBhbGwgdGhlIGBkZW5zZV9tb3ZpZV9pZGBzIGZvciB0aGUgbW92aWVzIHRoYXQgdXNlciA1MwpoYXMgbm90IHdhdGNoZWQuCgpgYGB7cn0KY3VzdG9tZXJfNTNfb3B0aW9ucyA8LSBleHBhbmQuZ3JpZCgKICB1c2VyX2lkID0gNTMsIAogIGRlbnNlX21vdmllX2lkID0gbW92aWVzX25vdF93YXRjaGVkCiAgKSAlPiUKICBhcy5tYXRyaXgoKQoKaGVhZChjdXN0b21lcl81M19vcHRpb25zKQpgYGAKCldlIGNhbiBub3cgZmVlZCB0aGlzIGluZm9ybWF0aW9uIGludG8gb3VyIGBwcmVkaWN0KClgIGZ1bmN0aW9uLiBSZW1lbWJlciwgb3VyCmtlcmFzIG1vZGVsIHRha2VzIHR3byBpbnB1dHMgKGB1c2VyX2lkYCAmIGBkZW5zZV9tb3ZpZV9pZGApIHNvIG91ciBgcHJlZGljdCgpYApmdW5jdGlvbiBpcyBnb2luZyB0byBleHBlY3QgYSBsaXN0IG9mIHR3byBpbnB1dHMgYXMgd2VsbC4KCmBgYHtyfQppbnB1dHMgPC0gbGlzdCgKICBjdXN0b21lcl81M19vcHRpb25zWywgInVzZXJfaWQiLCBkcm9wID0gRkFMU0VdLAogIGN1c3RvbWVyXzUzX29wdGlvbnNbLCAiZGVuc2VfbW92aWVfaWQiLCBkcm9wID0gRkFMU0VdCiAgKQoKcHJlZCA8LSBtb2RlbCAlPiUgcHJlZGljdChpbnB1dHMpCgpoZWFkKHByZWQpCmBgYAoKV2UgY2FuIG5vdyBhZGQgdGhlc2UgcHJlZGljdGlvbnMgdG8gb3VyIGBjdXN0b21lcl81M19vcHRpb25zYCBkYXRhLCBqb2luIHRoZQpgbW92aWVfb3B0aW9uc2AgZGF0YXNldCB0aGF0IGhhcyB0aGUgdGl0bGVzIGZvciB0aGUgbW92aWVzIGFuZCByYW5rLW9yZGVyIG91cgptb3ZpZXMgZm9yIHRob3NlIHRoYXQgaGF2ZSB0aGUgaGlnaGVzdCBleHBlY3RlZCByYXRpbmcuCgpgYGB7cn0KY3VzdG9tZXJfNTNfb3B0aW9ucyAlPiUKICBhc190aWJibGUoKSAlPiUKICBtdXRhdGUocHJlZGljdGlvbnMgPSBhcy52ZWN0b3IocHJlZCkpICU+JQogIGxlZnRfam9pbihtb3ZpZV9vcHRpb25zLCBieSA9ICJkZW5zZV9tb3ZpZV9pZCIpICU+JQogIGFycmFuZ2UoZGVzYyhwcmVkaWN0aW9ucykpCmBgYAoKIyBLZXkgdGFrZWF3YXlzCgoqIENvbGxhYm9yYXRpdmUgZmlsdGVyaW5nCiAgIC0gQSBjb21tb24gYW5kIHJlbGF0aXZlbHkgc2ltcGxlIGFwcHJvYWNoIHRvIG1ha2UgcmVjb21tZW5kYXRpb25zCiAgIC0gVGhlcmUgYXJlIG1hbnkgYWxnb3JpdGhtcyB0byBjaG9vc2UgZnJvbSBidXQgbWF0cml4IGZhY3Rvcml6YXRpb24gYW5kIG91cgogICAgIGRlZXAgbGVhcm5pbmcgZXh0ZW5zaW9uIGlzIHByb2JhYmx5IHRoZSBtb3N0IGNvbW1vbi4KICAgLSBBbGwgd2UncmUgZG9pbmcgaXMgCiAgICAgIDEuIGNyZWF0aW5nIGVtYmVkZGluZ3MgZm9yIGJvdGggb3VyIHVzZXJzIGFuZCBwcm9kdWN0cwogICAgICAyLiBkb3QgcHJvZHVjdCBtdWx0aXBsaWVzIHRoZXNlIG1hdHJpY2VzIG9mIGVtYmVkZGluZ3MKICAgICAgMy4gdXNlIGFkZGl0aW9uYWwgYmlhcyB3ZWlnaHRzIHRvIGFjY291bnQgZm9yIHVzZXIvcHJvZHVjdCBiaWFzZXMKICAgICAgNC4gYW5kIHdlIGNhbiBleHRlbmQgdGhpcyB3aXRoIHR5cGljYWwgZGVlcCBsZWFybmluZyBsYXllcnMgKGkuZS4gaGlkZGVuCiAgICAgICAgIGxheWVycywgZHJvcG91dCwgZXRjLikKKiBLZXJhcyBmdW5jdGlvbmFsIG1vZGVsCiAgIC0gQWxsb3dzIHVzIGZsZXhpYmlsaXR5IGluIGNyZWF0aW5nIGN1c3RvbSBtb2RlbHMKICAgLSBXZSBjYW4gaGF2ZSBtdWx0aXBsZSBpbnB1dHMgKGFuZCBzdWJzZXF1ZW50IGxheWVycykgYWxvbmcgd2l0aCBtdWx0aXBsZQogICAgIG91dHB1dHMKICAgLSBOYW1pbmcgb3VyIGxheWVycyBhbGxvd3MgdXMgdG8gZWFzaWx5IHZpZXcgdGhlIGxheWVyIGNvbm5lY3Rpb25zCiAgIC0gRm9yIG1vcmUgaW5mb3JtYXRpb24gb24ga2VyYXMnIGZ1bmN0aW9uYWwgbW9kZWwgc2VlOgogICAgICAtIFtEZWVwIExlYXJuaW5nIHdpdGggUl0oaHR0cHM6Ly9iaXQubHkvMlB2T3JCdiksIENoLiA3CiAgICAgIC0gW0d1aWRlIHRvIHRoZSBGdW5jdGlvbmFsIEFQSV0oaHR0cHM6Ly9iaXQubHkvMzV3WnFBeCk=